STraTOS 1997 April & May/STraTOS 1 - 1997 April & May.iso/CD01/INTERNET/SITES/RAND/ALL95.LZH/letters_tfb/text0008.txt

Text File | 1995-10-04 | 8.8 KB | 185 lines

>To: Laurent S.
>From: [e-mail] (Bertrand Le Roy)
>Subject: J'ai tout compris.
>Cc:
>Bcc:
>X-Attachments:
>
>Salut!
>
>En fait, la methode utilisΘe par doom est sans doute plus efficace que
celle que je proposais. Mais elle est moins facile a mettre en oeuvre. Je
pense qu'il faudra bouffer quelques sources car on ne trouvera pas toutes
les astuces tous seuls (a mon avis). J'aurai les sources de doom, mais je ne
peux pas dire quand.
>Alors voila. L'espace est divise en polygones CONVEXES. La raison est toute
simple, c'est que quand on est dans un polygone convexe, aucun mur ne peut
en cacher un autre. On peut donc les dessiner sans se preoccuper de rien. En
plus, ainsi, les sprites contenus dans ce polygone sont toujours devant tous
les murs => on n'a qu'a les dessiner en surimpression, apres avoir dessine
les murs, et le tour est joue. En plus, le format graphique permet de
dessiner avec des transprences, sans masque: les dessins sont organises en
colonnes, elles-memes separees en traits solides.
>La ou ca se gate, c'est qu'il y a des transparences. C'est pourquoi il y a
pour chaque niveau un arbre BSP qui indique ce qui est a droite et a gauche
de chaque separation de sous-secteur convexe.
>Je pense (mais c'est une premiere impression) qu'il faut dessiner le
sous-secteur ou est le joueur. Puis, pour chaque mur a deux face (donc
susceptible de donner une vue, par transparence, sur autre chose) visible,
on dessine les textures haute et basses (jamais transparentes IIRC), on
determine le secteur de l'autre cote, qu'on dessine, clippe par le trapeze
de notre mur a deux faces. Pour ce nouveau sous-secteur, on recommence la
meme chose, recursivement. Quand on a fini de dessiner un secteur, on
dessine les sprites qu'il contient, et on repasse la main au sous-secteur
appelant. Ce sous-secteur appelant peut maintenant dessiner son mur a deux
faces au-dessus du secteur fils qui vient d'etre dessine.
>Je pense que ca doit marcher, et assez vite. Un avantage (ou en est-ce un?)
est qu'on dessine chaque mur d'un seul coup. Un inconvenient est le clipping
selon un trapeze (les cotes droit et gauche sont bien sur verticaux). Mais
ca peut s'arranger en generalisant une partie de l'algo que j'avais suggere
la derniere fois dans mon bureau: tu peux gerer, pour chaque colonne, le
point le plus haut et le point le plus bas. Ca suffit. Et tu clippes chaque
colonne dessinee avec ces limites. D'ailleurs, si on fait ca, reduire la
taille de l'ecran revient simplement a chager les valeurs de depart de cette
table ;)
>Les plafonds, meme textures, peuvent entrer dans ce shΘma: on les dessine
juste apres les murs.
>Ceci dit, je pense qu'il doit y avoir de nombreuses optimisations a faire
sur ce schema. A mon avis, Webview doit etre la meilleure source a notre
disposition pour l'instant. En effet, ce programme a beneficie de la
participation de nombreuses personnes, les sources etant publics et
constament ameliores.
>Dis-moi ce que tu en penses.
>Je serai la lundi (peut-etre pas toute la journee ceci dit)
>
>Salut.
>Bertrand
>
>Tiens, j'ai recupere un texte assez interessant. L'algorithme propose est
un peu different:
>
>> misc. discussion deleted
>
>I've seen threads like this on c.g.a, doom-editing mailing
>list, r.g.p and else. There are lots of theories and
>descriptions (e.g. in the PCGPE), but nobody (expect
>the Id/Raven/...) guys really knows. There's even a
>disassembly of a pre-BSP beta of DOOM floating around...
>
>Now I'll do a quick description of *our* theory (which
>happens to be the approach we use :). Btw. we got some
>hints from people who have been/are now working for
>commercial companies, and even they do not agree ;-).
>
>
>a) wall rendering is done vertically, by one
>assembly loop, constant z, no divide, one table lookup
>for "fog"-like lighting remapping. Wall columns
>are stored as posts:
>
>   1 byte = starting row (in texture/pixmap space)
>   1 byte = number of non-transparent pixels
>   followed by all the non-transparent pixels
>
>DOOM treats opaque walls likes sprites and partly
>transparent wall patches.
>
>b) floor rendering is done horizontally (methinks),
>by another assembly loop (as in all but one direction,
>you'll go along u,v at an angle in texture space).
>Floor/ceilings textures are 64x64 pixel "flat" pixmaps
>only, no patches. They are stored using pixmap interleaving
>(flat1 row1, flat2 row1, flat3 row1, flat4 row1, flat1 row2...)
>which allows another texture mapping loop optimization.
>See Sean Barretts most recommended "Texture Mapping"
>description in the PCGPE.
>
>c) Restrictions are: only one floor, one ceiling per
>x,y - thus only one wall per x,y, always perpendicular
>to xy plane. If there's only one wall, there are
>only two differences in height possible between
>adjacent sectors (sounds familiar :), thus only
>an upper, a lower and a middle texture are possible
>on each side of the wall.
>Consequence: if you are rendering front-to-back, top
>will get "down" in each column only, and bottom will
>get "up". As soon as top >= bottom, column is done,
>as soon as all columns are done, fron-to-back is
>finished (do sprites/transparent middles now, below).
>
>d) Rendering is done using BSP traversal. During traversal,
>each subtree's bounding box is checked for intersection
>with the (2D) view volume (all DOOM stuff is 2D).
>If there's no intersection, subtree is completely outside
>of view, and discarded completely, or it is completely
>inside, skip further intersection checks (exepensive, too).
>If intersecting, continue checks during traversal.
>
>For each traversal step, you'll get a subsector (convex
>2D volume) i.e. a list of possibly visible walls. You
>have to sort in the sprites (that's the part I don't understand:
>BLOCKMAP only provides "ThingIsInSector" information, not
>the appropriate subsector - I dunno how to merge this) and
>clip them, but you put the sprites on some stack, for
>back-to-front later. You'll draw the wall per lineseg,
>draw lowers/upper and single-sided (non-transparent) middles
>(possibly partly transparent middle textures on stack, like
>sprites). For each of the seg's textures, you draw
>vertical columns. Now you'll get a gap to the last bottom (top)
>value for the first column of each lower (upper). These are the start
>columns of floor (ceiling) slices. The very last column of the same
>seg's lower texture provides you the end columns. You draw those
>slices immediately, but you have to keep track of top/bottom (as some
>wall drawn earlier on might hide (parts of) the floor). You
>use the upmost start, go towards end, and each time top is
>below, you have some slices finished, as the intersection
>provides ends for the slice. If top goes up next column, new
>starts. It *is* complicated to compare top/bottom clipping
>boundaries while doing horizontal slices, but, in a way,
>you are doing it on two edges of a four-vertex convex polygon
>only (the part of the floor "below" the current seg's lower
>texture).
>
>You traverse the BSP, rendering subsector's walls and floors/ceilings
>step by step, until all columns are done. Now you draw the
>pre-clipped visible sprite/transparent middle slices back-to-front
>from stack, painters algo. As soon as stack's empty, you're done
>with this frame.
>
>Phew.
>
>I know of a couple of alternatives (actually, we are trying to
>do it a bit different, and we are *still* working on the floors :-(,
>but that's the basic idea. If you are doing a complete BSP
>traversal to get a priority sorted polygon list, w/o any
>view volume clipping, or if you are doing floors back-to-front
>to fill gaps (especially the GUARD VAL polygon fill used in wt-0.04)
>you're likely to be slower. If you want to do more than one
>visible floor per x,y, or real 3D, or sprites/moving objects
>front-to-back, too, you'll have to maintain a list of
>already drawn parts of each screen column (for per column-rendering,
>or per row, alternatively, and completely different for polygon
>rendering, I guess :) and I don't think doing floors by row will work
>nice with having per-column-lookups...
>
>OK, hope this helps. Somebody mentioned DVIEW.ZIP to me, a C++ source
>on x2ftp.oulu.fi that does BSP traversal in a similar way, drawing
>floor in horizontal slices (but no texture mapping). Haven't looked
>at it.
>
>If anybody got a really good suggestion to do it else, please
>let me know.
>
+-----------------------------------------------------------+
|Bertrand Le Roy      |A Darwinian theory of Gravitation:   |
|[e-mail]|In the beginning,  mature apples fell|
|tel. [phone]     |in all directions. But only the trees|
|fax. [phone]     |whose apples fell down have survived.|
+-----------------------------------------------------------+
|Laboratoire de Gravitation et Cosmologie Relativistes      |
|Universite Pierre et Marie Curie, tour 22-12, 4e etage     |
|4, place Jussieu, 75252 Paris Cedex 05                     |
+-----------------------------------------------------------+